package com.fw.leetcode.dynamicprogram;

import com.fw.leetcode.LeetCode;

/**
 * 322. Coin Change
 *
 * You are given an integer array coins representing coins of different denominations and an integer amount
 * representing a total amount of money.
 *
 * Return the fewest number of coins that you need to make up that amount. If that amount of money cannot
 * be made up by any combination of the coins, return -1.
 *
 * You may assume that you have an infinite number of each kind of coin.
 *
 * Example 1:
 *  Input: coins = [1,2,5], amount = 11
 *  Output: 3
 *  Explanation: 11 = 5 + 5 + 1
 *
 * Example 2:
 *  Input: coins = [2], amount = 3
 *  Output: -1
 *
 * Example 3:
 *  Input: coins = [1], amount = 0
 *  Output: 0
 *
 * Constraints:
 *  1 <= coins.length <= 12
 *  1 <= coins[i] <= 2^31 - 1
 *  0 <= amount <= 10^4
 */
public class Num_0322 implements LeetCode {
    private interface Solution {
        int coinChange(int[] coins, int amount);

        default void assertEquals(int[] coins, int amount, int expected) {
            if (coinChange(coins, amount) != expected) {
                coinChange(coins, amount);
            }
        }
    }

    private static class MyDpRecursionSolution implements Solution {

        @Override
        public int coinChange(int[] coins, int amount) { // [超时未通过] 动态规划 + 递归
            /*
             * 零钱兑换
             * coins=[1,2,5], amount=11  =>  3 : 5+5+1
             *
             * f(amount) = 1 + min { f(amount-1), f(amount-2), f(amount-5) }
             * f(0) = 0
             * f(1) = 1
             * f(2) = 2
             */
            if (amount == 0) return 0;
            if (amount < 0) return -1;
            int minTimes = Integer.MAX_VALUE;
            for (int coin : coins) {
                int chg = coinChange(coins, amount - coin);
                if (chg == -1) {
                    continue;
                }
                int times = 1 + chg;
                if (times < minTimes) {
                    minTimes = times;
                }
            }
            return minTimes == Integer.MAX_VALUE ? -1 : minTimes;
        }
    }

    private static class MyDpIteratorSolution implements Solution {

        @Override
        public int coinChange(int[] coins, int amount) { // 最优：动态规划 + 数组迭代：时O(amount*coins) 空O(amount)
            /*
             * 零钱兑换
             * coins=[1,2,5], amount=11  =>  3 : 5+5+1
             *
             * f(amount) = 1 + min { f(amount-1), f(amount-2), f(amount-5) }
             * f(0) = 0  <- 固定
             * f(1) = 1
             * f(2) = 1
             */
            int[] times = new int[amount+1];
            for (int i = 1; i < times.length; i++) {
                // 求 times[i] 时的最小分配方案
                times[i] = Integer.MAX_VALUE;
                for (int coin : coins) {
                    if (i - coin >= 0 && times[i - coin] > -1) { // -1 时，对后面的计算无贡献
                        times[i] = Math.min(times[i], 1 + times[i - coin]);
                    }
                }
                if (times[i] == Integer.MAX_VALUE) { // 无分配方案，标记 -1
                    times[i] = -1;
                }
            }
            return times[amount];
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyDpIteratorSolution();
        solution.assertEquals(new int[]{1,2,5}, 11, 3);
        solution.assertEquals(new int[]{1,2,5}, 100, 20);
        solution.assertEquals(new int[]{2}, 3, -1);
        solution.assertEquals(new int[]{1}, 0, 0);
    }
}
